#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct TAreaForNum
{
	int area;
	int num;

	friend ostream& operator<<(ostream& ost, const TAreaForNum& r);
};

ostream& operator<<(ostream& ost, const TAreaForNum& r)
{
	ost << "{" << r.area << ", " << r.num << "}\n";

	return ost;
}

int main()
{
	TAreaForNum tCfg[] = {
		{11000, 40},
		{8000, 30},
		{400, 24},
		{800, 20},
		{900, 14},
		{1800, 16},
		{1000, 15},
		{7000, 40},
		{100, 10},
		{300, 12}
	};
	int arrNum = sizeof(tCfg) / sizeof(TAreaForNum);
	int totalArea[150] = { 0 };
	vector<int> vecIdx[150];

	totalArea[tCfg[0].num] = tCfg[0].area;
	vecIdx[tCfg[0].num].push_back(0);

	for (int i = 1; i < arrNum; i++)
	{
		int area = tCfg[i].area;
		int num = tCfg[i].num;

		for (int j = 150 - num - 1; j >= 0; j--)
		{
			/************************************************************/
			/*	假设原数据是这样的：(100, 30), (200, 20), (300, 30)		*/
			/*  那么第一次执行结果是：a[30] = 100 */
			/*      第二次执行的结果是：a[20] = 200, a[30] = 100, a[50] = 300 */
			/*      第三次执行的结果应是：a[20] = 200, a[30] = 300, a[50] = 500, a[60] = 300, a[80] = 600 */
			if (totalArea[j] != 0)
			{
				int afterArea = totalArea[j] + area;
				int afterNum = j + num;
				if (afterNum < 150 && afterArea > totalArea[afterNum])
				{
					totalArea[afterNum] = afterArea;
					vecIdx[afterNum].assign(vecIdx[j].begin(), vecIdx[j].end());
					vecIdx[afterNum].push_back(i);
				}
			}
		}

		//update
		if (area > totalArea[num])
		{
			totalArea[num] = area;
			vecIdx[num].assign(1, i);
		}
	}

	int *maxArea = max_element(totalArea, totalArea + 150);
	int maxIdx = distance(totalArea, maxArea);
	for_each(vecIdx[maxIdx].begin(), vecIdx[maxIdx].end(), [&tCfg](const int i) -> void {cout << tCfg[i]; });

	return 0;
}
